package com.suanfa.dfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author jukg
 * @date 2025/01/07 16:13
 * @description
 * 第一行输入m和n，m代表地图的长度，
 * n代表地图的宽度第二行开始具体输入地图信息，
 * 地图信息包含:
 * 0 为通畅的道路
 * 1 为障碍物 (且仅1为障碍物)
 * 2 为小华或者小为，地图中必定有且仅有2个(非障碍物)
 * 3 为被选中的聚餐地点 (非障碍物)
 */
public class HappyWeekend {

    static int personFlag = 2;
    static int targetFlag = 3;
    static int disableFlag = 1;

    static int[][] DIRECT = {{-1, 0},{1, 0},{0, 1},{0, -1}};
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        System.out.println("map size x: ");
        int m = scanner.nextInt();
        System.out.println("map size y: ");
        int n = scanner.nextInt();
        int[][] map = new int[m][n];
        // 显式读取行尾的换行符
        scanner.nextLine();*/
        int m =4, n =4;
        int[][] map = {{2,1,0,3},{0,1,2,1},{0,3,0,0},{0,0,0,0}};

        List<int[]> person = new ArrayList<>();
        List<int[]> target = new ArrayList<>();
        person.add(new int[]{0, 0});
        person.add(new int[]{2, 1});
        target.add(new int[]{0, 3});
        target.add(new int[]{2, 1});
        /*for(int i =0; i<m; i++){
            for(int j =0; j< n; j++){
                int input = scanner.nextInt();
                map[i][j] = input;
                if(input == personFlag){
                    person.add(new int[]{i, j});
                }
                if(input == targetFlag){
                    target.add(new int[]{i, j});
                }
            }
        }
        System.out.println("map x: y:");
        // 显式读取行尾的换行符
        scanner.nextLine();*/
        int[][] visited = new int[m][n];
        //前提条件两个人是否可以相遇
        if(dfs(person.get(0)[0], person.get(0)[1], person.get(1)[0], person.get(1)[1], visited, map)){
            int point = 0;
            for(int[] tar : target){
                visited = new int[m][n];
                if(dfs(person.get(0)[0], person.get(0)[1], tar[0], tar[1], visited, map)){
                    point ++;
                }
            }
            System.out.println(point);
        }
        System.out.println("0");
    }


    public static boolean dfs(int startX, int startY, int targetX, int targetY, int[][] visited, int[][] map){
        if(startX == targetX && startY == targetY){
            return true;
        }
        for(int[] direct: DIRECT){
            startX += direct[0];
            startY += direct[1];
            if(startX< 0 || startY <0 || startX> map.length || startY > map[0].length|| map[startX][startY] == disableFlag
                    || visited[startX][startY] == 1){
                continue;
            }
            visited[startX][startY] = 1;
            dfs(startX,startY, targetX, targetY,visited, map);
        }
        return false;

    }



}
